ICPC Live Archive/3928 - Ballroom lights/3928.2.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <cstdio>
   4 #include <list>
   5 #include <utility>
   6 #include <cstdlib>
   7 #include <cassert>
   8 #include <complex>
   9
  10 #define forn(i, n) for (int i = 0; i < (n); i++)
  11 #define EPS 1e-8
  12
  13 using namespace std;
  14
  15 struct Vector {
  16     long double x;
  17     long double y;
  18
  19     Vector(long double xi, long double yi): x(xi), y(yi) {};
  20
  21     long double length()  {
  22         return hypot(x, y);
  23     }
  24
  25     long double angle() {
  26         return atan2(y, x);
  27     }
  28
  29 };
  30
  31 struct Column {
  32     Vector position;
  33     long double radius;
  34
  35     Column(long double x, long double y, long double r) : position(x,y), radius(r) {};
  36 };
  37
  38 typedef Vector Lamp;
  39 typedef pair<long double, long double> Interval;
  40 typedef pair<Vector, Vector> Segment;
  41
  42
  43 inline long double length(const Segment& s) {
  44     return Vector(s.second.x - s.first.x, s.second.y - s.first.y).length();
  45 }
  46
  47 inline long double length(const Interval& i) {
  48     assert(i.first <= i.second);
  49     return i.second - i.first;
  50 }
  51
  52
  53 pair< long double, bool > intersect_segments(const Segment& s1, const Segment& s2) {
  54     Vector p1 = s1.first;
  55     Vector p2 = s1.second;
  56     Vector p3 = s2.first;
  57     Vector p4 = s2.second;
  58
  59     long double den = (p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y);
  60
  61     long double ua_num = (p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
  62     long double ub_num = (p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
  63
  64     if (fabs(den) < EPS) {
  65         // Caso en que los Segments son paralelos
  66         if (fabs(ua_num - ub_num) < EPS && fabs(ub_num) < EPS) {
  67             // Las rectas son coincidentes, esto no deberia ocurrir
  68             assert(false);
  69         }
  70         return make_pair(0, false);
  71     }
  72
  73     if (ub_num/den >= 0) {
  74         return make_pair(ua_num/den, true);
  75     }
  76     return make_pair(0, false);
  77 }
  78
  79
  80 Interval intersect_intervals(const Interval& i1, const Interval& i2) {
  81
  82     long double d0 = max(i1.first, i2.first);
  83     long double d1 = min(i1.second, i2.second);
  84
  85     if (d1 < d0) {
  86         return Interval(0, 0);
  87     } else {
  88         return Interval(d0, d1);
  89     }
  90 }
  91
  92
  93 Interval dark_range(const Segment& wall, const Lamp& lamp, const Column& column) {
  94     Vector bisectriz(column.position.x - lamp.x, column.position.y - lamp.y);
  95     long double p = asin(column.radius/bisectriz.length());
  96     long double alpha = bisectriz.angle();
  97
  98     Vector d1(cos(alpha + p), sin(alpha + p));
  99     Vector d2(cos(alpha - p), sin(alpha - p));
 100
 101     pair< long double, bool > p1 = intersect_segments(wall, Segment(lamp, Vector(lamp.x + d1.x, lamp.y + d1.y)));
 102     pair< long double, bool > p2 = intersect_segments(wall, Segment(lamp, Vector(lamp.x + d2.x, lamp.y + d2.y)));
 103
 104     long double wall_length = length(wall);
 105
 106     // Se sabe que los puntos de interseccion estan ordenados correctamente
 107     // porque el angulo de diferencia entre las semirectas es menor a 180,
 108     // entonces no es necesario chequearlo.
 109     Interval res;
 110
 111     if (!p1.second) {
 112         if (!p2.second) {
 113             return Interval(0, 0);
 114         } else {
 115             res = Interval(0, p2.first);
 116         }
 117     } else {
 118         if (!p2.second) {
 119             res = Interval(p1.first, 1);
 120         } else {
 121             res = Interval(p1.first, p2.first);
 122         }
 123     }
 124
 125     res = intersect_intervals(res, Interval(0,1));
 126     return Interval(res.first * wall_length, res.second * wall_length);
 127 }
 128
 129 void invert_range(const list<Interval>& ints, long double fin, list<Interval>& out) {
 130
 131     if (!ints.size()) {
 132         out.push_back(Interval(0,fin));
 133         return;
 134     }
 135
 136
 137     list<Interval>::const_iterator it = ints.begin();
 138     if (it->first > 0) {
 139         out.push_back(Interval(0, it->first));
 140     }
 141
 142     it++;
 143
 144     list<Interval>::const_iterator itprev = ints.begin();
 145     while (it != ints.end()) {
 146         out.push_back(Interval(itprev->second, it->first));
 147         it++;
 148         itprev++;
 149     }
 150
 151     if (itprev->second < fin) {
 152         out.push_back(Interval(itprev->second, fin));
 153     }
 154 }
 155
 156
 157 void reduce_union(list<Interval>& l_o, list<Interval>& out) {
 158     // elimino repetidos para acelerar el sort
 159     list<Interval> l;
 160
 161     for (list<Interval>::const_iterator it = l_o.begin(); it != l_o.end(); it++) {
 162         if (it->first < it->second) {
 163             l.push_back(Interval(it->first, it->second));
 164         } else if (it->first > it->second) {
 165             assert(false);
 166         }
 167     }
 168
 169
 170     if (!l.size()) return;
 171
 172     l.sort();
 173
 174     list<Interval>::const_iterator it = l.begin();
 175     Interval cand = *it;
 176     Interval other;
 177
 178     it++;
 179     while (it != l.end()) {
 180         other = *it;
 181         if (other.first < other.second) {
 182             if (other.first > cand.second) {
 183                 out.push_back(cand);
 184                 cand = other;
 185             } else {
 186                 if (other.second > cand.second) {
 187                     cand = Interval(cand.first, other.second);
 188                 }
 189             }
 190         }
 191         it++;
 192     }
 193
 194     out.push_back(cand);
 195 }
 196
 197
 198 long double solve(const list<Lamp>& lamps, const list<Column>& columns, int max_x, int max_y) {
 199     list<Segment> walls;
 200     walls.push_back(Segment(Vector(max_x,0), Vector(0, 0)));
 201
 202     long double total = 0;
 203
 204     for (list<Segment>::iterator p = walls.begin(); p != walls.end(); p++) {
 205         list<Interval> lit_on_this_wall;
 206         for (list<Lamp>::const_iterator l = lamps.begin(); l != lamps.end(); l++) {
 207             list<Interval> dark_zones;
 208             for (list<Column>::const_iterator c = columns.begin(); c != columns.end(); c++) {
 209                 dark_zones.push_back(dark_range(*p, *l, *c));
 210             }
 211
 212             list<Interval> merged_dark_zones;
 213             list<Interval> lit_zone;
 214
 215             reduce_union(dark_zones, merged_dark_zones);
 216             invert_range(merged_dark_zones, length(*p), lit_zone);
 217
 218             lit_on_this_wall.splice(lit_on_this_wall.end(), lit_zone);
 219         }
 220
 221         list<Interval> merged_lit_on_this_wall;
 222         reduce_union(lit_on_this_wall, merged_lit_on_this_wall);
 223
 224         for (list<Interval>::iterator it = merged_lit_on_this_wall.begin(); it != merged_lit_on_this_wall.end(); it++) {
 225             total += length(*it);
 226         }
 227     }
 228
 229     return total;
 230 }
 231
 232
 233 int main() {
 234
 235     int nl, nc, max_x, max_y;
 236
 237     for (;;) {
 238         scanf("%d %d %d %d", &nl, &nc, &max_x, &max_y);
 239
 240         if (!(nl || nc || max_x || max_y)) {
 241             break;
 242         }
 243
 244         list<Vector> lamps;
 245         list<Column> columns;
 246
 247         int x, y, r;
 248
 249         forn(i, nl) {
 250             scanf("%d %d", &x, &y);
 251             lamps.push_back(Lamp(x,y));
 252         }
 253
 254         forn(i, nc) {
 255             scanf("%d %d %d", &x, &y, &r);
 256             columns.push_back(Column(x, y, r));
 257         }
 258
 259         printf("%.4Lf\n", solve(lamps, columns, max_x, max_y));
 260     }
 261 }